<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>658. 找到 K 个最接近的元素</title>
  </head>
  <body>
    <script>
      //     给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

      // 整数 a 比整数 b 更接近 x 需要满足：

      // |a - x| < |b - x| 或者
      // |a - x| == |b - x| 且 a < b
      //

      // 示例 1：

      // 输入：arr = [1,2,3,4,5], k = 4, x = 3
      // 输出：[1,2,3,4]
      // 示例 2：

      // 输入：arr = [1,2,3,4,5], k = 4, x = -1
      // 输出：[1,2,3,4]

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/find-k-closest-elements
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
      /**
       * @param {number[]} arr
       * @param {number} k
       * @param {number} x
       * @return {number[]}
       */
      var findClosestElements = function (arr, k, x) {
        let res = []
        let i = 0
        for (; i < arr.length; i++) {
          // 找出插入数组arr的哪个位置
          if (arr[i] > x) {
            break
          }
        }
        if (i === 0) {
          // 当插入在头
          res = arr.splice(0, k)
          return res
        }
        if (i === arr.length) {
          // 当插入在尾部
          res = arr.splice(arr.length - k)
          return res
        }
        // 插入中间值
        let leftNum = 1
        let rightNum = 0
        let left = arr[i - leftNum]
        let right = arr[i + rightNum]
        while (k > 0) {
          if (right - x < x - left) {
            res.push(right)
            rightNum++
          } else {
            res.unshift(left)
            leftNum++
          }
          k--
          if (leftNum > i) {
            // 左边到头
            left = -Infinity
          } else {
            left = arr[i - leftNum]
          }
          if (rightNum > arr.length - i - 1) {
            // 右边到头
            right = Infinity
          } else {
            right = arr[i + rightNum]
          }
        }
        return res
      }
      console.log(findClosestElements([1, 2, 3, 4, 5], 4, -1))
    </script>
  </body>
</html>
